๐Ÿ‘ฉโ€๐Ÿ’ป 16472. ๊ณ ๋ƒฅ์ด

@Seongukbaek Posted May 14, 2022 ยท Updated May 14, 2022 ยท 5 min read

๋ฌธ์ œ

๊ณ ์–‘์ด๋Š” ๋„ˆ๋ฌด ๊ท€์—ฝ๋‹ค. ์‚ฌ๋žŒ๋“ค์€ ๊ณ ์–‘์ด๋ฅผ ๋„ˆ๋ฌด ๊ท€์—ฌ์›Œํ–ˆ๊ณ , ๊ฒฐ๊ตญ ๊ณ ์–‘์ด์™€ ๋”์šฑ ๊ฐ€๊นŒ์›Œ์ง€๊ณ  ์‹ถ์–ด ๊ณ ์–‘์ด์™€์˜ ์†Œํ†ต์„ ์œ„ํ•œ ๊ณ ์–‘์ด ๋ง ๋ฒˆ์—ญ๊ธฐ๋ฅผ ๋ฐœ๋ช…ํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค. ์ด ๋ฒˆ์—ญ๊ธฐ๋Š” ์‚ฌ๋žŒ์˜ ์–ธ์–ด๋ฅผ ๊ณ ์–‘์ด์˜ ์–ธ์–ด๋กœ, ๊ณ ์–‘์ด์˜ ์–ธ์–ด๋ฅผ ์‚ฌ๋žŒ์˜ ์–ธ์–ด๋กœ ๋ฐ”๊พธ์–ด ์ฃผ๋Š” ํฌ๋Œ€์˜ ๋ฐœ๋ช…ํ’ˆ์ด ๋  ๊ฒƒ์ด๋‹ค.

ํ˜„์žฌ ๊ณ ์–‘์ด๋ง ๋ฒˆ์—ญ๊ธฐ์˜ ๋ฒ ํƒ€๋ฒ„์ „์ด ๋‚˜์™”๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ด ๋ฒ ํƒ€๋ฒ„์ „์€ ์™„์ „ ์—‰๋ง์ง„์ฐฝ์ด๋‹ค. ๋ฒ ํƒ€๋ฒ„์ „์˜ ๋ฒˆ์—ญ๊ธฐ๋Š” ๋ฌธ์ž์—ด์„ ์ฃผ๋ฉด ๊ทธ ์ค‘์—์„œ ์ตœ๋Œ€ N๊ฐœ์˜ ์ข…๋ฅ˜์˜ ์•ŒํŒŒ๋ฒณ์„ ๊ฐ€์ง„ ์—ฐ์†๋œ ๋ฌธ์ž์—ด๋ฐ–์— ์ธ์‹ํ•˜์ง€ ๋ชปํ•œ๋‹ค. ๊ต‰์žฅํžˆ ๋ณ„๋กœ์ง€๋งŒ ๊ทธ๋‚˜๋งˆ ์ด๊ฒŒ ์ตœ์„ ์ด๋ผ๊ณ  ์‚ฌ๋žŒ๋“ค์€ ์ƒ๊ฐํ–ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ์ด ๋ฒˆ์—ญ๊ธฐ๊ฐ€ ์ธ์‹ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋Š” ์–ผ๋งˆ์ธ์ง€๊ฐ€ ๊ถ๊ธˆํ•ด์กŒ๋‹ค.

๊ณ ์–‘์ด์™€ ์†Œํ†ตํ•  ์ˆ˜ ์žˆ๋„๋ก ์šฐ๋ฆฌ๋„ ํ•จ๊ป˜ ๋…ธ๋ ฅํ•ด๋ณด์ž.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์—๋Š” ์ธ์‹ํ•  ์ˆ˜ ์žˆ๋Š” ์•ŒํŒŒ๋ฒณ์˜ ์ข…๋ฅ˜์˜ ์ตœ๋Œ€ ๊ฐœ์ˆ˜ N์ด ์ž…๋ ฅ๋œ๋‹ค. (1 < N โ‰ค 26)
  • ๋‘˜์งธ ์ค„์—๋Š” ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค ๋ฌธ์ž์—ด์˜ ๊ธธ์ด โ‰ค 100,000) ๋‹จ, ๋ฌธ์ž์—ด์—๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋งŒ์ด ํฌํ•จ๋œ๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— ๋ฒˆ์—ญ๊ธฐ๊ฐ€ ์ธ์‹ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ž์—ด์˜ ์ตœ๋Œ€๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

while(left <= right) { // ๋ฒ”์œ„ ๋ฒ—์–ด๋‚˜๋ฉด ์ข…๋ฃŒ, ๊ธฐ๋ณธ์ ์œผ๋กœ right๊ฐ€ ๋จผ์ € ์›€์ง์ž„ if (right >= str.length()) break; char rightCh = str.charAt(right); if ((left != right || right == 0) && prev == left) wordIndexMap.put(rightCh, wordIndexMap.getOrDefault(rightCh, 0) + 1); // ์•„์ง N๊ฐœ ์ดํ•˜์ธ ๊ฒฝ์šฐ, ๊ณ„์† length๋ฅผ ๋Š˜๋ฆผ if (wordIndexMap.size() <= N) { maxLength = Math.max(maxLength, right - left + 1); right++; prev = left; } else { // N๊ฐœ๊ฐ€ ์ฑ„์›Œ์ ธ ๊ธฐ์กด์˜ ์ข…๋ฅ˜๋ฅผ ํ•˜๋‚˜ ์ œ์™ธํ•˜๋Š” ๊ฒฝ์šฐ char leftCh = str.charAt(left); int num = wordIndexMap.get(leftCh) - 1; if(num == 0) wordIndexMap.remove(leftCh); else wordIndexMap.put(leftCh, num); left++; } }
  • Map ์œผ๋กœ ์•ŒํŒŒ๋ฒณ ์ข…๋ฅ˜์™€ ๋นˆ๋„ ์ˆ˜๋ฅผ ์ €์žฅํ•œ๋‹ค.
  • Map ์ด N size๊ฐ€ ๋œ ๊ฒฝ์šฐ์™€ ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ , right ๋ฅผ ๋Š˜๋ฆฌ๋ฉด์„œ ๊ธธ์ด๋ฅผ ์ฆ๊ฐ€์‹œํ‚ค๊ฑฐ๋‚˜ Map ์—์„œ ๊ธฐ์กด ์•ŒํŒŒ๋ฒณ ํ•˜๋‚˜๋ฅผ ์ง€์šด๋‹ค.

    • ์ด๋•Œ, left ์— ์œ„์น˜ํ•œ ๋ฌธ์ž์—ด์— ๋Œ€ํ•ด Map ์—์„œ ์กฐํšŒํ•ด๋ณด๊ณ , left ๋ฅผ ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class Cat { int maxLength = 0; public Cat() {} public void translate(int N, String str) { Map<Character, Integer> wordIndexMap = new HashMap<>(); int left = 0; int right = 0; int prev = left; while(left <= right) { // ๋ฒ”์œ„ ๋ฒ—์–ด๋‚˜๋ฉด ์ข…๋ฃŒ, ๊ธฐ๋ณธ์ ์œผ๋กœ right๊ฐ€ ๋จผ์ € ์›€์ง์ž„ if (right >= str.length()) break; char rightCh = str.charAt(right); if ((left != right || right == 0) && prev == left) wordIndexMap.put(rightCh, wordIndexMap.getOrDefault(rightCh, 0) + 1); // ์•„์ง N๊ฐœ ์ดํ•˜์ธ ๊ฒฝ์šฐ, ๊ณ„์† length๋ฅผ ๋Š˜๋ฆผ if (wordIndexMap.size() <= N) { maxLength = Math.max(maxLength, right - left + 1); right++; prev = left; } else { // N๊ฐœ๊ฐ€ ์ฑ„์›Œ์ ธ ๊ธฐ์กด์˜ ์ข…๋ฅ˜๋ฅผ ํ•˜๋‚˜ ์ œ์™ธํ•˜๋Š” ๊ฒฝ์šฐ char leftCh = str.charAt(left); int num = wordIndexMap.get(leftCh) - 1; if(num == 0) wordIndexMap.remove(leftCh); else wordIndexMap.put(leftCh, num); left++; } } } public int getMaxLength() { return maxLength; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); String str = br.readLine(); Cat cat = new Cat(); cat.translate(N, str); System.out.println(cat.getMaxLength()); } }

โœ๏ธ Review

  • ํˆฌ ํฌ์ธํ„ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์•Œ๊ฒŒ ๋˜์–ด ์•„์ด๋””์–ด๋Š” ์‰ฝ๊ฒŒ ์žก์„ ์ˆ˜ ์žˆ์—ˆ์œผ๋‚˜ ๊ตฌํ˜„์—์„œ ์กฐ๊ธˆ ๋ง‰ํ˜”๋‹ค.
  • right ๋ฅผ ๋Š˜๋ฆฌ๋ฉด์„œ prev ๋ฅผ ํ™•์ธํ•ด์ฃผ๋Š” ๊ณผ์ •์ด ํ•„์š”ํ–ˆ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€